佇列其資料結構用圖片來說明大概如下:
資料以一列的方式儲存每個資料,而且刪除節點時會從最前面也是最早加入佇列的資料開始刪除,新增節點從佇列尾巴開始刪除。此為佇列 先進先出(FIFO, First-In-First-Out) 的特性。
佇列只允許在後端(稱為Rear)進行插入操作,在前端(稱為Front)進行刪除操作
佇列的兩種操作函式:
常見範例:
對於佇列有初步了解後,我們來實作吧!這裡使用 Linked List 當作基礎的資料結構去做實作。
先定義出Queue類別及它的節點
class QueueNode {
constructor(data, next) {
this.data = data
this.next = next
}
}
class Queue {
constructor() {
this.front = null
this.tail = null
}
// 判斷佇列是否為空,直接判斷最前面節點是否為空即可
isEmpty() {
return this.front === null
}
// 新增節點
enqueue(value) {
}
// 移除節點
dequeue() {
}
}
邏輯相當的簡單,記得是從尾巴新增節點喔~
enqueue(value) {
let node = new QueueNode(value)
if (this.isEmpty()) {
this.front = node
this.tail = node
} else {
// 讓尾巴節點先指向node新節點
this.tail.next = node
// 讓新節點變成新的尾巴節點
this.tail = node
}
}
將原本前面第二個節點變成第一個節點即可
dequeue() {
let result = this.front.data
// 空佇列的狀況
if (this.isEmpty()) {
return null
}
if (this.front === this.tail) { // 變成空佇列
this.front = null
this.tail = null
} else {
// 使原本前面第二個節點變成第一個節點
this.front = this.front.next
}
return result
}
最後建立 qq 物件,並使用enqueue()和dequeue()進行操作
let qq = new Queue()
qq.enqueue("A")
qq.enqueue("B")
qq.enqueue("C")
qq.enqueue("D")
qq.enqueue("E")
while (!qq.isEmpty()) {
console.log(qq.dequeue()) // A B C D E
}
可參考 Time and Space Complexity of Queue
這次文章的程式碼在以下連結:
https://github.com/a90100/javascript-data-structure/blob/master/day8-queue.js
以上就是這次關於佇列的介紹,明天我們將用佇列解決一個找質數問題!